package lhc.alg.top100;

/**
 * description: https://leetcode.cn/problems/maximum-swap/
 *  最大交换 贪心算法
 * author: hongchen.liao
 * date:  2022/9/11
 */
public class _670_ {

    class Solution {
        public int maximumSwap(int num) {
            String s = String.valueOf(num);
            int len = s.length();
            char[] charArr = s.toCharArray();
            //记录每个数字最后一次出现的下标
            int[] last = new int[10];
            for(int i = 0; i < len; i++){
                last[charArr[i]-'0'] = i;
            }
            //从左到右扫描 找到当前位置右边的最大的数字并交换
            for(int i = 0; i < len-1; i++){
                //找最大 所以倒着找
                for(int d = 9; d > charArr[i]-'0'; d--){
                    if(last[d] > i){
                        swap(charArr, i, last[d]);
                        //只允许交换一次 直接返回
                        return Integer.parseInt(new String(charArr));
                    }
                }
            }
            return num;
        }

        void swap(char[] charArr, int i, int j){
            char t = charArr[i];
            charArr[i] = charArr[j];
            charArr[j] = t;
        }
    }

}
